package com.peng.leetcode.tree;

/**
 * ConstructMaximumBinaryTree1
 * 654. 最大二叉树
 * https://leetcode.cn/problems/maximum-binary-tree/
 * <p>
 * Created on 2022/12/3
 *
 * @author lupeng
 */
public class ConstructMaximumBinaryTree1 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int index = findMaxIndex(nums, start, end);
        TreeNode root = new TreeNode(nums[index]);
        root.left = build(nums, start, index - 1);
        root.right = build(nums, index + 1, end);
        return root;
    }

    int findMaxIndex(int[] nums, int start, int end) {
        int i = start;
        for (int j = i; j < (end + 1); j++) {
            if (nums[i] < nums[j]) {
                i = j;
            }
        }
        return i;
    }
}
